class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if len(word)==0:
            return False
        letterDict = {}
        nRow = len(board)
        nCol = len(board[0])
        for r in range(len(board)):
            for c in range(len(board[0])):
                ch = board[r][c]
                if ch not in letterDict:
                    letterDict.update({ch:[]})
                letterDict[ch].append((r,c))
        neighbourhood = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        coordSet = set()
        def traverse(coord, begin):
            if begin==len(word):
                return True
            coordSet.add(coord)
            result = False
            for c in neighbourhood:
                neighbour = (coord[0]+c[0], coord[1]+c[1])
                if 0<=neighbour[0]<nRow and \
                    0<=neighbour[1]<nCol and \
                    board[neighbour[0]][neighbour[1]]==word[begin] and \
                    neighbour not in coordSet:
                    result = result or traverse(neighbour, begin+1)
            coordSet.remove(coord)
            return result
        if word[0] in letterDict:
            for coord in letterDict[word[0]]:
                if traverse(coord, 1):
                    return True
        return False

board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
print(Solution().exist(board, "ABCB"))